package com.algorithm.sort;

import java.util.Arrays;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * @description 快速排序
 * 参考：https://blog.csdn.net/Holmofy/article/details/71168530
 * @program: sudy
 * @description:
 * @author:
 * @create: 2020-01-05 11:28
 **/
public class QuickSort {

    public static void main(String[] args) {

//        int[] array = {11, 8, 3, 9, 7, 1, 5, 2, 1};
        int[] array = {4, 2, 6, 1, 3, 5, 7};
        quickSort(array, 0, array.length - 1);
        for (int n : array) {
            System.out.println(n);
        }

//        System.out.println(topK(array, 0, array.length - 1, 3));

//        List<Integer> list = new ArrayList() {
//            {
//                add(12);
//                add(20);
//                add(12);
//                add(22);
//                add(22);
//                add(23);
//                add(159);
//                add(12);
//            }
//        };
//
//        Map<Integer, Long> map = Arrays.stream(array).boxed().collect(Collectors.groupingBy(p -> p,
//                Collectors.counting()));
//        System.out.println(map.get(1));
//
//
//        Map<Integer, Long> mapA = list.stream().collect(Collectors.groupingBy(p -> p, Collectors.counting()));


    }

    public final static void quickSort(int[] array, int from, int to) {
        int partition = partition2(array, from, to);
//        int partition = partition2(array, from, to);
        if (partition > -1) {
            quickSort(array, from, partition - 1);
            quickSort(array, partition + 1, to);
        }
    }

    /**
     * 功能描述: 获取第K大个元素
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/6 10:36 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/6 10:36 上午
     **/
    public final static int topK(int[] array, int from, int to, int k) {

        if (k < 0 || k > array.length) {
            throw new IllegalArgumentException();
        }

        int partition = partition(array, from, to);
        if (partition > -1) {
            if (partition + 1 == k) {
                return array[partition];
            }

            /**
             * 位于左半区
             */
            if (partition + 1 > k) {
                return topK(array, from, partition - 1, k);
            } else {
                return topK(array, partition + 1, to, k);
            }


        }

        return -1;
    }

    /**
     * @Description: 数组分区方法
     * 一端挖坑，一端埋
     * @Param: [array, from, to]
     * @return: void
     * @Author: kukuxiahuni
     * @Date: 2020/1/5
     */
    public final static int partition(int[] array, int from, int to) {

        if (array == null || from > to) {
            return -1;
        }

        int pivot = array[from];

        int i = from, j = to;

        while (i < j) {

            //1. 从右向左找到比监视哨小的值，进行交换
            while (i < j && pivot < array[j]) {
                --j;
            }

            if (i < j) {
                array[i++] = array[j];
            }

            while (i < j && pivot > array[i]) {
                ++i;
            }

            if (i < j) {
                array[j--] = array[i];
            }
        }

        array[i] = pivot;
        return i;

    }


    /**
     * @Description: 分区方式
     * 单向扫描划分方式
     * 1. 取数组最后一位为哨兵；
     * 2. 使用哨兵对[0, to-1]的数组进行分区
     * 3. 令 i=j = from
     * 4. 当array[j] < pivot时， i与j的数值进行交换（将小的值前移） ； ++i
     * 5. 当j=to时，一趟排序完成；交换i和to位置的元素；i为分区位置。
     * @Param: [array, from, to]
     * @return: int
     * @Author: kukuxiahuni
     * @Date: 2020/1/5
     */
    public final static int partition2(int[] array, int from, int to) {

        if (from > to || array == null) {
            return -1;
        }

        int pivot = array[to];
        int i = from;

        for (int j = from; j <= to - 1; j++) {
            if (array[j] < pivot) {
                swap(array, i, j);
                ++i;
            }
        }

        swap(array, i, to);
        return i;


    }

    /**
     * @Description:
     * @Param: [array, a, b]
     * @return: void
     * @Author: kukuxiahuni
     * @Date: 2020/1/5
     */
    public final static void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    public final static void testPriorityQueue() {
        int[] array = {11, 8, 3, 9, 7, 1, 5, 2, 1};
        Map<Integer, Long> map = Arrays.stream(array)
                .boxed()
                .collect(Collectors.groupingBy(p -> p, Collectors.counting()));
        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (a, b) -> {
                    return (int) (map.get(a) - map.get(b));
                }
        );
    }

    /**
     * 功能描述: 两端扫描交换排序
     * 两种方式：
     * 1. 如果i <= j : 进行交换时，i++， j--
     * 2. 如果i < j : 进行交换时，不需要
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 2:31 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 2:31 下午
     **/
    public final static int doubleEndPartition(int[] array, int start, int end) {

        if (start > end) {
            return -1;
        }

        int i = start, j = end;
        /**
         * 构建轴
         */
        int pivot = array[start];
        while (i < j) {


            /**
             * 从后向前扫描:寻找比pivot小的值;也就是当 pivot > array[j]的时候，停止循环
             */
            while (i < j && pivot < array[j]) {
                --j;
            }

            /**
             * 从前向后扫描：寻找比pivot大的值
             */
            while (i < j && pivot > array[i]) {
                ++i;
            }

            if (i < j) {
                swap(array, i, j);
//                ++i;
//                --j;
            }
        }
        /**
         * 交换轴位
         */
        swap(array, start, j);
        return j;
    }

    /**
     * 功能描述: 同上
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/12 3:32 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/12 3:32 下午
     **/
    public final static int xxx(int[] array, int start, int end) {
        if (start >= end) {
            return -1;
        }

        int i = start, j = end + 1;
        int pivot = array[start];

        while (i < j) {

            while (i < j && pivot < array[--j]) {
            }

            while (i < j && pivot > array[++i]) {
            }

            if (i < j) {
                swap(array, i, j);
            }
        }

        swap(array, start, i);
        return i;
    }
}
